# -*- coding:utf8 -*-

# 804
def uniqueMorseRepresentations(words):
    """
    :type words: List[str]
    :rtype: int
    """
    code_list = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
    
    results = set()
    for word in words:
        result = ''
        for letter in word:
            result += code_list[ord(letter) - 97]
        print result
        results.add(result)            
    return len(results)

# 804
def uniqueMorseRepresentations2(words):
    code_list = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

    return len({''.join(code_list[ord(letter) - ord('a')] for letter in word) for word in words})

# 832
def flipAndInvertImage(A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        # return [[ 0 if i == 1 else 1 for i in a][::-1] for a in A]
        # return [[ 1 ^ i for i in a][::-1] for a in A]
        return [[ 1 - i for i in a][::-1] for a in A]
# 807
def maxIncreaseKeepingSkyline(grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        result = 0
        for index in range(len(grid)):
            for i in range(len(grid[index])):
                target = min(max(grid[index]),max([g[i] for g in grid]))
                if grid[index][i] <= target:
                    result += (target - grid[index][i])
        return result

#807
def maxIncreaseKeepingSkyline2(grid):
    row,col = map(max,grid),map(max,*grid)
    return sum(min(i,j) for i in row for j in col) - sum(map(sum,grid))

# 797
def allPathsSourceTarget(graph):
    def dfs(cur,path):
        if cur == len(graph) - 1:
            res.append(path)
        else:
            for i in graph[cur]:
                dfs(i,path + [i])
    
    res = []
    dfs(0,[0])
    return res

# 657
def judgeCircle(moves):
        """
        :type moves: str
        :rtype: bool
        """
        kv = {
            'L':2,
            'R':-2,
            'U':1,
            'D':-1
        }
        
        result = 0
        for m in moves:
            result += kv[m]
        
        if result == 0:
            return True
        
        return False

# 728
def selfDividingNumbers(left, right):
        """
        :type left: int
        :type right: int
        :rtype: List[int]
        """
        # result = []
        # for i in range(left,right+1):
        #     num = str(i)
        #     if '0' in num:
        #         continue
        #     elif len(num) == 0:
        #         result.append(i)
        #         continue
        #     else:
        #         total = len(num)
        #         trys = 0
        #         for n in num:
        #             if i % int(n) == 0:
        #                 trys+=1
        #             else:
        #                 pass
        #         if total == trys:
        #             result.append(i)
        # return result
        is_divide_num = lambda num:'0' not in str(num) and all((num % int(digit) == 0 for digit in str(num)))
        return filter(is_divide_num,range(left,right+1))

def selfDividingNumbers2(left, right):
    is_dividing_number = lambda x : all([True if int(letter) != 0 and x % int(letter) == 0 else False for letter in str(x)])
    return list(filter(is_dividing_number,range(left,right+1)))

# 561
def arrayPairSum(nums):
    nums = sorted(nums)
    return sum([min(nums[i:i+2]) for i in range(0,len(nums))[::2]])

# 763
def partitionLabels(S):
    sizes = []
    while S:
        i = 1
        while set(S[:i]) & set(S[i:]):
            i += 1
        sizes.append(i)
        S = S[i:]
    return sizes

# 476
def findComplement(num):
    # TODO 用位运算再试下
    return int(''.join([str(1-int(i)) for i in str(bin(num)[2:])]),2)

# 806
def numberOfLines(widths, S):
    res, cur = 1, 0
    for s in S:
        width = widths[ord(s)-ord('a')]
        res += 1 if cur + width > 100 else 0
        cur = width if cur + width > 100 else cur + width
        # if sum + width == 100:
        #     result.append(sum + width)
        #     sum = 0
        # elif sum + width > 100:
        #     result.append(sum)
        #     sum = width
        # else:
        #     sum += width
    # result.append(sum)

    return [res, cur]

# 811
def subdomainVisits(cpdomains):
        """
        :type cpdomains: List[str]
        :rtype: List[str]
        """
        result = {}

        for item in cpdomains:        
            times,domain = item.split(" ")
            times = int(times)
            result[domain] = times if domain not in result else result[domain]+times
            _,p2 = domain.split('.',1)
            result[p2] = times if p2 not in result else result[p2]+times
            if '.' in p2:
                result[p2.split('.')[-1]] = times if p2.split('.')[-1] not in result else result[p2.split('.')[-1]]+times
        
        return ['%s %s'%(result[item],item) for item in result]

def subdomainVisits2(cpdomains):
    c = collections.Counter()
    for cd in cpdomains:
        n, d = cd.split()
        c[d] += int(n)
        for i in range(len(d)):
            if d[i] == '.': c[d[i + 1:]] += int(n)
    return ["%d %s" % (c[k], k) for k in c]

# 338
def countBits(num):
        """
        :type num: int
        :rtype: List[int]
        """
        return [bin(i).count('1') for i in range(num+1)]

def countBits(num):
    res = [0]
    for i in xrange(1,num+1):
        res.append(res[i>>1] + (i&1))
    return res

# 821
def shortestToChar(S, C):
    ol = len(S)
    result = []
    temp = []
    in_middle = False
    for i,s in enumerate(S):
        temp.append(s)
        if s == C:
            if in_middle:
                length = len(temp) - 1
                subresult = [i for i in xrange(1,length/2+1)]
                if length % 2 == 0:
                    result += subresult + subresult[::-1]
                else:
                    result += subresult + [(length + 1) / 2] +subresult[::-1]
                result += [0]
            else:
                result += reversed([i for i in range(len(temp))])
            S = S[i:]
            temp = []
            in_middle = True
    
    if len(result) < ol:
        if S:
            print S
            if C in S:
                S = S[1:]
            result += [i for i in xrange(1,len(S)+1)]

    return result

def shortestToChar2(S, C):
    n = len(S)
    res = [n]*n
    pos = -n
    for i in range(n) + range(n)[::-1]:
        if S[i] == C:pos = i
        res[i] = min(res[i],abs(i - pos))
    return res
# 344
def reverseString(s):
    return s[::-1]

def reverseString2(s):
    l = len(s)
    if l < 2:
        return s
    else:
        return reverseString2(s[l/2:]) + reverseString2(s[:l/2])

def reverseString3(s):
    result = []
    length = len(s)
    for i in range(length):
        result.append(s[length - 1 - i])

    return ''.join(result)

def reverseString4(s):
    r = list(s)
    i,j = 0,len(r) - 1
    if i < j:
        r[i],r[j] = r[j],r[i]
        i += 1
        j -= 1
    
    return ''.join(r)

def reverseString5(s):
    r = list(s)
    for i in range(len(r) // 2):
        r[i],r[~i] = r[~i],r[i]
    return ''.join(r)

# 557
def reverseWords(s):
        """
        :type s: str
        :rtype: str
        """
        S = s.split(' ')
        result = []
        for item in S:
            result.append(reverseString(item))
        
        return ' '.join(result)

        # return ' '.join([ item[::-1] for item in s.split(' ')])

def reverseWords2(s):
    return ' '.join(s.split()[::-1])[::-1]

# 500
def findWords(words):
    S1 = set("qwertyuiop")
    S2 = set("asdfghjkl")
    S3 = set("zxcvbnm")
    result = []
    for item in words:
        if set(item.lower()) - S1 == set():
            result.append(item)
            continue
        if set(item.lower()) - S2 == set():
            result.append(item)
            continue
        if set(item.lower()) - S3 == set():
            result.append(item)
            continue
    
    return result

# 用正则
def findWords2(words):
    import re
    return filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match,words)

# 575
def distributeCandies(candies):
        return min(len(candies) / 2,len(set(candies)))

# 412
def fizzBuzz(n):
    result = []
    for item in range(1,n+1):
        if item % 15 == 0:
            result.append("FizzBuzz")
        elif item % 3 == 0:
            result.append("Fizz")
        elif item % 5 == 0:
            result.append("Buzz")
        else:
            result.append("%s" % item)
    
    return result

# 566
def matrixReshape(nums, r, c):
    if len(nums) * len(nums[0]) != r * c:
        return nums
    else:
        new = []
        map(new.extend,nums)
        
        result = []
        start = 0
        end = c
        for i in range(r):
            result.append(new[start:end])
            start = end
            end += c
        return result


if __name__ == '__main__':
    # print uniqueMorseRepresentations(["rwjje","aittjje","auyyn","lqtktn","lmjwn"])
    # print uniqueMorseRepresentations2(["rwjje","aittjje","auyyn","lqtktn","lmjwn"])
    # print flipAndInvertImage([[1,1,0],[1,0,1],[0,0,0]])
    # print maxIncreaseKeepingSkyline([[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]])
    # print maxIncreaseKeepingSkyline2([[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]])
    # print allPathsSourceTarget([[1,2],[3],[3],[]])
    # print judgeCircle('ULLURDLU')
    # print selfDividingNumbers(1,4352)
    # print arrayPairSum([1,4,3,2])
    # print partitionLabels('ababcbacadefegdehijhklij')
    # print findComplement(5)
    # D = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
    # print numberOfLines(D,'bbbcccdddaaa')
    # L = ['9001 discuss.leetcode.com','900 google.mail.com']
    # print subdomainVisits(L)
    # print subdomainVisits2(L)
    # print countBits(5)
    # print shortestToChar("loveleetcode","e")
    # print shortestToChar("pkvhaagbqk","a")
    # print reverseString5('hello')
    # print reverseWords2("Let's take LeetCode contest")
    # print findWords2(["Hello", "Alaska", "Dad", "Peace"])
    # print distributeCandies([1,1,2,3])
    # print fizzBuzz(15)
    print matrixReshape([[1,2],[3,4]],2,2)